home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8228 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.2 KB
  1. Path: spock.ebt.com!gtn
  2. From: gtn@ebt-inc (Gavin Nicol)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Counting high bits  (was (no subject))
  5. Date: 02 Mar 1996 15:12:22 GMT
  6. Organization: Electronic Book Technologies, Inc.
  7. Distribution: world
  8. Message-ID: <GTN.96Mar2101222@ebt-inc>
  9. References: <4gv493$p09@nuacht.iol.ie> <4h5bin$i2t@ccshst05.cs.uoguelph.ca>
  10. NNTP-Posting-Host: ebt-inc.ebt.com
  11. In-reply-to: thay@uoguelph.ca's message of 29 Feb 1996 23:07:03 GMT
  12.  
  13. If you know the size of the data that you are trying to count bits in,
  14. a simple way is to use a table. This is also quite fast.
  15.  
  16. /*
  17.  * count bits using a table
  18.  */
  19.  
  20. static char bit_table[256] = {
  21.   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  22.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  23.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  24.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  25.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  26.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  27.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  28.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  29.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  30.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  31.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  32.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  33.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  34.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  35.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  36.   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  37. };
  38.  
  39. int count_bits_table(unsigned long x)
  40. {
  41.     unsigned char *ptr = (unsigned char *)&x;
  42.  
  43.     return(bit_table[ptr[0]] + bit_table[ptr[1]] + 
  44.            bit_table[ptr[2]] + bit_table[ptr[3]] );
  45. }
  46.  
  47. The most esoteric one I have ever seen is HACKMEM, for X11 source code:
  48.  
  49. int count_bits_hackmem(unsigned long x)
  50. {
  51.     register unsigned long tmp;
  52.  
  53.     tmp = (x >> 1) &033333333333;
  54.     tmp = x - tmp - ((tmp >>1) & 033333333333);
  55.     return ((unsigned int) (((tmp + (tmp >> 3)) & 030707070707) % 077));
  56. }
  57. --
  58.  
  59. Gavin Thomas Nicol                | He who will not reason, is a bigot;
  60. Electronic Book Technologies      | he who cannot is a fool; 
  61. Email:      gtn@ebt.com           | and he who dares not is a slave. 
  62. Phone/FAX:  +81-3-3706-7351       |       --- Sir William Drummond
  63.  
  64.